The trichromatic nature of human color vision requires three color primaries for reproducing color images. In the digital image processing art it usually takes 8 to 10 bits per color to render a high quality color image. However, there are many low-cost color monitors which have only 8-bit frame buffers. Although they have 8 or 10-bit digital-to-analog converters for the red, green, blue electron guns, and, given proper calibration, are capable of showing 2.sup.24 or 2.sup.30 colors, their frame buffers can only accommodate 8-bits per pixel thereby limiting the number of possible displayable colors at a given frame to 2.sup.8 =256. With the help of a colormap lookup table (256 entries, each 24-bit deep), these 256 colors can be chosen from any of the 2.sup.24 possible colors. The problem is how to choose the appropriate 256 colors to render a color image with the least objectionable artifacts. A number of methods have been proposed to solve the problem of 24-to-8-bit color reduction. These methods have been designed with explicit goals to minimize certain cost functions of colorimetric errors based on the statistical distribution of the colors in the input image.
The median-cut, the mean-cut, and the variance-based algorithms are typical examples of such error-minimization methods. The median-cut and the mean-cut algorithms were described by P. Heckbert, "Color image quantization for the frame buffer display," Computer Graphics, 16, 3, 297-307, 1982. The variance-based algorithm was described by S. J. Wan, P. Prusinkiewicz, and S. K. M. Wong, "Variance-based color image quantization for frame buffer display," COLOR research and application, 15, 1, 52-58, 1990. The basic idea behind all the three existing methods is to recursively partition the RGB color histogram into smaller and smaller sub-boxes so that each of the final 256 sub-boxes can be represented by its mean color without large errors. The three methods differ in how the sub-boxes are selected and partitioned. The median-cut and the mean-cut methods select the sub-box that has the largest dynamic range for further partitioning. The mean-cut algorithm partitions it at the mean value and the median-cut at the median value. In comparison, the variance-based method selects the sub-box that has the largest variance for further partitioning, and it partitions the sub-box at the point that produces the minimum sum of the variances of the resulting two smaller boxes.
Another variation of the above method is to form the color histogram in the "uniform" color space, such as CIELAB or CIELUV, so that the human perceptual error, rather than camera sensor error, is minimized. This was described by R. S. Gentile, J. P. Allebach, and E. Walowit, "Quantization of color images based on uniform color spaces," Journal of Imaging Technology, 16, 1, 11-21, 1990.
Although the idea of minimizing color errors seems to be intuitively sound, the above mentioned solutions overlook the following empirical findings that can improve the color rendition even further: The world consists of separate objects whose surfaces reflect light in a way that could be approximated by some reflection models. The human visual system does not perceive the world as unrelated color patches that happen to fit into an image. Instead, it insists on interpreting the image as consisting of objects reflecting different color light. The consequence of this persistent cognitive interpretation is the tendency for us to ignore the color variations within an object surface and to emphasize those between different objects. Color errors are more difficult to see in a busy area than in a uniform area. The large dynamic range of a color scene is mainly due to illumination variations from one part of the scene to another. Luminance range across a surface is usually much smaller except when there is a shadow. Rendering an image region of an object surface thus requires much fewer levels of shades.
A patent of interest for its teaching is U.S. Pat. No. 4,907,075 entitled "Method for Selecting Colors" by G. W. Braudaway wherein an RGB histogram is formed and the most populated cell is selected as the representation color. The method then reduces the neighboring cell counts by an exponential function before it picks the next representation color. Another patent of interest is U.S. Pat. No. 5,049,986 entitled "Method And Apparatus For Color Image Quantization" by M. Aono et al. This patent relates to a data structure that allows a fast implementation of an algorithm similar to the one disclosed in the previous patent, U.S. Pat. No. 4,907,075.